# coding=utf-8
# Date: 2021/9/14 9:30
from typing import List


# 执行用时：572 ms, 在所有 Python3 提交中击败了20.21%的用户
# 内存消耗：16.3 MB, 在所有 Python3 提交中击败了68.12%的用户
class Solution:
    def findLongestWord(self, s: str, dictionary: List[str]) -> str:
        res = ""
        for word in dictionary:
            if not self.check(s, word):
                continue
            if len(res) < len(word) or (len(res) == len(word) and word < res):
                res = word
        return res

    def check(self, a, b):
        i, j = 0, 0
        while i < len(a) and j < len(b):
            if a[i] == b[j]:
                j += 1
            i += 1
        return j == len(b)


if __name__ == "__main__":
    print(Solution().findLongestWord("abpcplea", ["ale", "apple", "monkey", "plea"]))
